
# 归并排序
def sort_list(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    a = sort_list(lst[mid:])
    b = sort_list(lst[:mid])
    return merge(a, b)

def merge(a,b):
    c = []
    while a and b:
        if a[0] <= b[0]:
            c.append(a.pop(0))
        else:
            c.append(b.pop(0))
    c += a + b
    return c

if __name__ == '__main__':
    lst = [10, 98, 99, 35, 2, 68, 79, 89]
    print(sort_list(lst))
